In packet-switched data communication systems it is often advantageous that the data transfer packets to be transferred are classified as belonging to different quality-of-service classes (CoS, Class of Service) according to the kind of requirements the applications using the data communications service have and, on the other hand, according to the kind of agreements (SLA, Service Level Agreement) on the service quality that the data communications service provider has made with its customers using data communications services. For example, concerning a telephone application, such as an Internet call, it is essential that the data transfer speed required by the application is available for the time required, that the data transfer delay is sufficiently small, and that the variation of the transfer delay is sufficiently small. In a telephone application it is not useful that the data transfer speed provided for the application could be momentarily increased when the load in the data transfer network is reduced. Instead, for example when uploading a web site, it is extremely advantageous if even a momentarily free capacity of the data transfer network can be efficiently utilized.
It is often advantageous that the data transfer packets arrived at a certain network element or the data transfer packets created in this network element, which are heading towards the same destination but represent different quality-of-service classes, are transferred to said destination via different routes. The information of quality-of-service class identifying the quality-of-service class can be included in the data transfer packet that arrives at the network element controlling the traffic, or said quality-of-service class can be created in said network element based on the packet classification. In connection with the IP networks (IP, Internet Protocol), the term ‘router’ is generally used for the network element controlling the traffic. For illustrating the background of the invention, FIG. 1 shows an exemplifying packet-switched data transfer network, which comprises terminal devices 101-106 and traffic controlling network elements 111-115. The terminal device 101 sends data transfer packets 121 and 122 directed to the terminal device 102 to the data transfer network. The data transfer packets 121 belong to the quality-of-service class CoS1 and represent a delay-critical traffic flow, which requires a low transfer capacity, for example 64 Kbit/s. The data transfer packets 122 belong to the quality-of-service class CoS2 and represent a traffic flow which is not delay-critical but requires a notably higher transfer capacity, for example 100 Mbit/s. In this exemplifying situation, the destination address related to the data transfer packets 121 is the address of the terminal device 102 and the information of quality-of-service is the information identifying the quality-of-service class CoS1. Correspondingly, the destination address related to the data transfer packets 121 is the address of the terminal device 102 and the information of quality-of-service is the information identifying the quality-of-service class CoS2. In such a situation it is worthwhile routing the data transfer packets 121 from the network element 111 to the network element 112 via a transfer link 131, because in this case the route between the terminal devices 101 and 102 has as few delay-causing network elements as possible and, on the other hand, the data transfer capacity of 100 Mbit/s of the link 131 is well sufficient for very many simultaneous traffic flows of 64 Kbit/s. It is worthwhile routing the data transfer packets 122 from the network element 111 to the network element 112 via transfer links 132, 133 and 134, of which each has a data transfer capacity of 1 Gbit/s, because in this case the data transfer capacity of the route between the terminal devices 101 and 102 is as high as possible. In the network element 111, a routing decision is made which identifies the data transfer link to be used in forwarding the data transfer packet. The routing decision can be made separately for each packet (packet-by-packet forwarding) or the same routing decision can be used for more than one packet directed to the same destination and representing the same quality-of-service class (stateful forwarding). Said routing decision depends on both the destination address (DA) related to the data transfer packet and the quality-of-service class that this data transfer packet represents.
In addition to the routing decision related to forwarding of the data transfer packet, it is also possible to create verification data related to a security measure. Said security measure (RAL, Reverse Address Lookup) is used to verify whether the data transfer packet has arrived from such an area of the data transfer network that corresponds to the source address (SA) indicated in this data transfer packet. The verification data related to the security measure is created in a similar way as the routing decision but using the source address instead of the destination address. Said security measure can be used to prevent such hostile network attacks which have been implemented with data transfer packets having an untrue source address indicated in them. The verification data related to the security measure can also depend, besides on the source address, on the quality-of-service class represented by the data transfer packet.
Later in this document, both the routing decision related to forwarding and the verification data related to the security measure are referred to with ‘routing data’.
The information related to the data transfer packet which is used together with the information of quality-of-service class for creating the routing data, can also be some other information related to the applied data transfer protocol than the source address and the destination address mentioned in the above example.
Later in this document, a general term ‘protocol data’ is used when referring to the information, related to the data transfer packet, which is used together with the information of quality-of-service class in creating the routing data and whose type or value depend on the data transfer protocol used. Said protocol data can be for instance an IPv4 source address (Internet Protocol version 4), an IPv6 source address (Internet Protocol version 6), a TCP source port number (Transmission Convergence Protocol), a UDP source port number (User Datagram Protocol), an IPv4 destination address, an IPv6 destination address, a TCP destination port number, a UDP destination port number, an ATM-VC/VP number (Asynchronous Transfer Mode, Virtual Circuit/Virtual Path), a Frame Relay DLCI (Data Link Connection Identifier), an MPLS label (Multi Protocol Label Switching), information identifying the data transfer protocol used, or a combination of two or more above mentioned pieces of information.
The data transfer link which the routing data refers to can be either a physical data transfer link, such as an optical fiber or a radiolink, or a logical transfer link, such as an IP tunnel configured for a physical data transfer link. Furthermore, in multicast transfer the routing data can refer to more than one data transfer link.
Theoretically, a lineal solution for creating routing data dependent on the quality-of-service class would be a Random Access Memory (RAM) device, for which the memory address to be assigned would be defined by attaching the information of quality-of-service to the protocol data. Said routing data would be provided as the output data of this memory device. The size of the address space of said random access memory device should be at least 2N+M, where N is the word width of the information of quality-of-service in bits and M is the word width of the protocol data in bits. For example, if the protocol data is an IPv4 destination or source address, the word width of the protocol data is 32 bits. In equipment implementations, reservation is typically made for eight different quality-of-service classes. Consequently, the word width of the information of quality-of-service class is 3 bits. With the present implementation technology of random access memories it is not reasonable to attempt implementation of an address space with a size of 235. If the protocol data is an IPv6 destination or source address, the word width of the protocol data is as many as 128 bits.
One piece of equipment according to the prior art technique for creating routing data dependent on the quality-of-service class in packet-switched data transfer is shown in FIG. 2. The equipment comprises a Ternary Content Access Memory (TCAM) device 201. The address data used for the TCAM memory device 201 is a combination of the protocol data (PA) and the quality-of-service class (CoS) 203. The output data 205 of the TCAM memory device 201 is used as the address data of a random access memory device 202. The routing data 204 is the output data of the random access memory device 202. Some of the characteristics of the equipment are set forth below in connection with an IPv4 protocol that uses classless addresses (CIDR, Classless InterDomain Routing), when the number of different quality-of-service classes is eight and an IPv4 source or destination address is used as the protocol data (PA).
In routing dependent on the quality-of-service class, each pair, composed of the subnet prefix and the routing data of the routing table to be supported, is associated with a condition of quality-of-service class, which expresses the quality-of-service classes that those data transfer packets represent for which this pair composed of the subnet prefix and the routing data concerned is valid. The information of quality-of-service class CoS can be expressed with three bits, since in this exemplifying situation the number of quality-of-service classes is eight. In the implementation based on a TCAM memory device, said condition of quality-of-service class is expressed as a conditioning vector, which has as many elements as the information of quality-of-service class has bits. Each element of the conditioning vector indicates whether the bit of the information of quality-of-service class must be one or zero or whether this bit can be either of them. For example, if the quality-of-service classes 0, 2, 4 and 6 are acceptable quality-of-service classes, the corresponding conditioning vector would be (*, *, 0), which means that the least meaningful bit of the information of quality-of-service class must be zero and the other two bits can be either zero or one. In this case the condition of quality-of-service class can thus be expressed with one conditioning vector. However, for a certain condition of quality-of-service class more than one conditioning vector is often required, since acceptable quality-of-service classes cannot always be expressed with one conditioning vector. For example, if the quality-of-service classes 1, 2 and 6 are acceptable quality-of-service classes, three conditioning vectors (0,0,1), (0,1,0) and (1,1,0) are required.
The TCAM memory device 201 is used to implement a table, which has the subnet prefix of the routing table to be supported and the conditioning vector as well as the output data of the TCAM memory device corresponding these stored in each of its rows. These rows have a priority order relative to each other. The output data 205 provided by the TCAM memory device corresponds to the row, which has the highest priority of the rows in which the stored subnet prefixes and conditioning vectors correspond to the combination 203 of the protocol data PA and the information of quality-of-service class CoS assigned as the address information. With a suitable mutual prioritizing of the rows it is possible to implement for instance a longest prefix match search dependent on the quality-of-service class (CoS aware longest prefix match).
The size and the price of a TCAM memory device depend on the number of the required rows and the required row length, i.e. the amount of information to be stored in each row. The number of required rows is the number of subnet prefixes of the routing table to be supported multiplied with the average number of conditioning vectors per each subnet prefix. Said average number of conditioning vectors per each subnet prefix means the number of conditioning vectors, which is required on average for expressing a condition of quality-of-service class related to one subnet prefix.
A memory device of the TCAM type is essentially more expensive than a random access memory device of the same size, where the size of the memory device means the product of the address space size and the word width of the output data. In addition, the power consumption of a TCAM type memory device is notably higher than the power consumption of a random access memory device of the same size and which is used with a similar reading frequency. For these reasons, in practical applications it is endeavoured that the size of the TCAM type memory device is as small as possible.
Another piece of equipment according to the prior art technique for creating routing data dependent on the quality-of-service class is shown in FIG. 3. The equipment comprises a TCAM memory device 301. As the address data of the TCAM memory device 301, protocol data 303 (PA) is used. As the address data of a random access memory device 302, the combination of the output data 305 (SR) of the TCAM memory device 301 and the information of quality-of-service class 306 (CoS) is used. The routing data 304 is the output data of the random access memory device 302. In the equipment illustrated in FIG. 3, the effect of the quality-of-service class on the routing data is created by means of the random access memory device 302. For example, in connection with the classless IPv4 routing, the TCAM memory device 301 can be used to perform a normal longest prefix match search independent on the quality-of-service class.
Let us examine a situation in which it is required that each of the devices illustrated in FIGS. 2 and 3 must be capable of supporting the same routing table, and let us assume that the device shown in FIG. 2 requires N conditioning vectors on average per subnet prefix. In this case the TCAM memory device 301 shown in FIG. 3 can be more than N times smaller than the TCAM memory device 201 shown in FIG. 2. That the size ratio is larger than N is due to the fact that conditioning vectors need not be stored in the TCAM memory device 301. On the other hand, the random access memory device 302 shown in FIG. 3 must be larger than the random access memory device 202 shown in FIG. 2, since routing data must be stored in the random access memory device 302 for each combination composed of the subnet prefix and the information of quality-of-service class. Thus, the random access memory device 302 shown in FIG. 3 must be essentially larger than the random access memory device 202 shown in FIG. 2, whereupon a large part of the savings, which are achieved by the reducing size required of the TCAM memory device, is lost as the size required of the random access memory device increases.
The TCAM memory devices shown in FIGS. 2 and 3 can be replaced with an algorithmic search engine. An algorithmic search engine can be implemented using random access memory devices, which are more cost-effective than the content addressable memory devices and the power consumption of which is lower than the power consumption of the content addressable memory devices. In methods based on algorithmic search engines, several successive memory searches are performed, the intermediate results of which are used as the basis in advancing in the logical search structure until a result corresponding to the initial data of the search, such as the protocol data or a combination of the protocol data and the information of quality-of-service class, is found. Algorithmic search engines known for those skilled in the art include, for example, a radix-trie, a Patricia-trie, an M-ary trie, and the Luleå algorithm (according to established practice, the term “trie”, for retrieval, is used here). An algorithmic search engine, which is capable of performing a search dependent on a quality-of-service class and which can be used to replace the TCAM memory device shown in FIG. 2, is at least functionally more complicated and requires a higher storage capacity than an algorithmic search engine, which only needs to perform a search independent of the quality-of-service class and which can be used to replace the TCAM memory device shown in FIG. 3. On the other hand, a large part of the savings, which are achieved by the simplification of the algorithmic search engine, is lost as the size required of the random access memory device increases in a similar way as in connection with the equipment based on the TCAM memory devices.
It is typical for the equipment and methods according to the prior art technique that the requirement for considering the quality-of-service class in creating the routing data essentially increases the storage capacity required of the equipment and thus often also the power consumption of the equipment. The increase of the required storage capacity increases the component costs, physical size and the production and testing costs of the equipment. Likewise, increased power consumption increases the physical size and costs of the equipment.